package com.剑指offer.第五章;


import java.util.HashMap;
import java.util.TreeMap;

/**
 * 使用哈希表+双向链表
 */
public class SimpleLRU {

    private HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();

    private ListNode head = null;

    private ListNode tail = null;

    private Integer capacity;

    public SimpleLRU(int capacity) {
        head = new ListNode(-1);
        tail = new ListNode(-1);

        // 前后使用哨兵节点
        head.next = tail;
        tail.pre = head;

        this.capacity = capacity;
    }

    /**
     * @return
     */
    public int get(int key) {
        ListNode listNode = map.get(key);
        if (listNode == null) {
            return 0;
        }

        moveTail(listNode);

        return listNode.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            moveTail(map.get(key));
        } else {
            if (map.size() == capacity) {
                ListNode dele = head.next;

                deleteNode(dele);
                map.remove(key);
            }

            ListNode listNode = new ListNode(value);

            insertTail(listNode);

            map.put(key, listNode);
        }
    }

    public void moveTail(ListNode node) {
        deleteNode(node);
//        node.val = value;
        insertTail(node);
    }

    public void deleteNode(ListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }


    public void insertTail(ListNode node) {
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

}
